package ru.susu.algebra.util;

import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import junit.framework.Assert;

import com.google.common.collect.Maps;

import ru.susu.algebra.pair.Pair;
import ru.susu.algebra.wrapper.number.INumberWrapper;

/**
 * @author akargapolov
 * @since: 09.03.2009
 */
public final class NumberUtilities
{
	public static int getLength(long number, int base)
	{
		int res = (number >= 0) ? 0 : 1;
		do
		{
			number /= base;
			res++;
		}
		while (number != 0);
		return res;
	}

	public static boolean isFullSquare(Integer[] array)
	{
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (Integer item : array)
		{
			for (Pair<Integer, Integer> pair : factorization(BigInteger.valueOf(item)))
			{
				Integer key = pair.getKey();
				Integer value = pair.getValue();
				if (!map.containsKey(key))
					map.put(key, value);
				else
				{
					Integer value1 = value + map.get(key);
					map.put(key, value1);
				}
			}
		}
		for (Map.Entry<Integer, Integer> entry : map.entrySet())
		{
			if (entry.getValue() % 2 != 0)
				return false;
		}
		return true;
	}

	/**
	 * Проверка числа на полный квадрат. Происходит разложение в произведение простых {@link #factorization(BigInteger)},
	 * затем проверяется четность каждой степени.
	 *
	 * @param number тестируемое число типа {@link BigInteger}
	 * @return true, если число является полным квадратом
	 */
	public static boolean isFullSquare(BigInteger number)
	{
		boolean result = true;
		for (Pair<Integer, Integer> pair : factorization(number))
		{
			result = result && (pair.getValue() % 2 == 0);
		}
		return result;
	}

	/**
	 * Проверка числа на вхождение в него квадратов.
	 * Происходит разложение натурального числа на множители {@link #factorization(BigInteger)}, затем
	 * проверяется уникальность каждого делителя.
	 *
	 * @param number проверяемое число типа {@link BigInteger}
	 * @return true, если число степени всех простых чисел в разложении равны единице
	 */
	public static boolean containsSquare(BigInteger number)
	{
		for (Pair<Integer, Integer> pair : factorization(number))
		{
			if (pair.getValue() > 1)
				return true;
		}
		return false;
	}

	/**
	 * Очистка числа от квадратов.
	 * @param number исходное число
	 * @return исходное число без квадратов
	 */
	public static BigInteger clearSquares(BigInteger number)
	{
		BigInteger result = BigInteger.valueOf(number.signum());
		for (Pair<Integer, Integer> pair : factorization(number.abs()))
		{
			if (pair.getValue() % 2 == 1)
			{
				result = result.multiply(BigInteger.valueOf(pair.getKey()));
			}
		}
		return result;
	}

	public static Map<Integer, Integer> factorization2Map(BigInteger number)
	{
		Map<Integer, Integer> map = Maps.newLinkedHashMap();
		for (Pair<Integer, Integer> pair : factorization(number))
		{
			map.put(pair.getKey(), pair.getValue());
		}
		return map;
	}

	public static Pair<Integer, Integer>[] factorization(BigInteger n)
	{
		if (n.equals(BigInteger.ZERO))
		{
			return (Pair<Integer, Integer>[]) Array.newInstance(Pair.class, 0);
		}
		List<Pair<Integer, Integer>> result = new ArrayList<Pair<Integer, Integer>>();

		int factor = getFactorPow(n, BigInteger.valueOf(2));
		if (factor != 0)
		{
			result.add(new Pair<Integer, Integer>(2, factor));
			for (int j = 0; j < factor; j++)
				n = n.divide(BigInteger.valueOf(2));
		}
		BigInteger sqrt = squareRoot(n);
		for (BigInteger i = BigInteger.valueOf(3); i.compareTo(sqrt) <= 0; i = i.add(BigInteger.valueOf(2)))
		{
			factor = getFactorPow(n, i);
			if (factor != 0)
			{
				result.add(new Pair<Integer, Integer>(i.intValue(), factor));
				for (int j = 0; j < factor; j++)
					n = n.divide(i);
				sqrt = squareRoot(n);
			}
		}
		if (!n.equals(BigInteger.ONE))
		{
			result.add(new Pair<Integer, Integer>(n.intValue(), 1));
		}
		Pair<Integer, Integer>[] array = (Pair<Integer, Integer>[]) Array.newInstance(Pair.class, result.size());
		result.toArray(array);
		return array;
	}

	public static int getFactorPow(BigInteger n, BigInteger factor)
	{
		int res = 0;
		while (n.remainder(factor).equals(BigInteger.ZERO))
		{
			res++;
			n = n.divide(factor);
		}
		return res;
	}

	public static BigInteger getFactorial(int n)
	{
		BigInteger res = BigInteger.ONE;
		for (int i = 2; i <= n; i++)
			res = res.multiply(BigInteger.valueOf(i));
		return res;
	}

	public static <T> INumberWrapper<T> scalarProduct(INumberWrapper<T>[] first, INumberWrapper<T>[] second)
	{
		INumberWrapper<T> result = first[0].multiply(second[0]);
		for (int index = 1;index < first.length;index++)
			result = result.add(first[index].multiply(second[index]));
		return result;
	}

	/**
	 * Метод Ньютона-Рафсона для вычисления квадратного корня из числа
	 * http://e-maxx.ru/algo/roots_newton
	 *
	 * @param number исходное число
	 * @return квадратный корень
	 */
	public static BigInteger squareRoot(BigInteger number)
	{
		BigInteger a = BigInteger.ONE.shiftLeft (number.bitLength() / 2);
		boolean p_dec = false;
		while (true)
		{
			BigInteger b = number.divide(a).add(a).shiftRight(1);
			if (a.compareTo(b) == 0 || a.compareTo(b) < 0 && p_dec)
				break;
			p_dec = a.compareTo(b) > 0;
			a = b;
		}
		return a;
	}

	/**
	 * Переводит число в строку, печатает знак + если нужно
	 * @param number число
	 * @param printPlusSign необходимость знака +
	 * @param printOne печатать единицу или нет
	 * @return строковое представление числа со знаком
	 */
	public static String toString(BigInteger number, boolean printPlusSign, boolean printOne)
	{
		if (number.compareTo(BigInteger.ZERO) >= 0 && printPlusSign)
		{
			return "+" + toString(number, printOne);
		}
		return toString(number, printOne);
	}

	private static String toString(BigInteger number, boolean printOne)
	{
		if (number.abs().equals(BigInteger.ONE))
		{
			return printOne ? number.toString() : (number.equals(BigInteger.ONE) ? "" : "-");
		}
		return number.toString();
	}

	public static BigInteger lcm(Collection<BigInteger> numbers)
	{
		BigInteger result = BigInteger.ONE;
		for (BigInteger number : numbers)
		{
			BigInteger gcd = result.gcd(number);
			result = result.multiply(number).divide(gcd);
		}
		return result;
	}

	public static BigInteger product(Collection<BigInteger> numbers)
	{
		BigInteger result = BigInteger.ONE;
		for (BigInteger number : numbers)
		{
			result = result.multiply(number);
		}
		return result;
	}

	private static final int MATRIX_SIZE = 100;
	private static final BigInteger[][] _cnk = new BigInteger[MATRIX_SIZE + 1][MATRIX_SIZE + 1];

	public static BigInteger cnk(int n, int k)
	{
		Assert.assertTrue(n <= MATRIX_SIZE);

		if (_cnk[n][k] != null)
		{
			return _cnk[n][k];
		}

		BigInteger result = BigInteger.ONE;
		for (int i = 1; i <= k; i++)
		{
			result = result.multiply(BigInteger.valueOf(n - i + 1));
			result = result.divide(BigInteger.valueOf(i));
		}
		_cnk[n][k] = result;
		return result;
	}

	private static final Map<Integer, BigInteger> _bellNumbers = Maps.newHashMap();

	public static BigInteger bellNumber(int n)
	{
		Assert.assertTrue(n >= 0);
		if (n <= 1)
		{
			return BigInteger.ONE;
		}
		if (_bellNumbers.containsKey(n))
		{
			return _bellNumbers.get(n);
		}
		BigInteger result = BigInteger.ZERO;
		for (int k = 0; k < n - 1; k++)
		{
			result = result.add(cnk(n, k).multiply(bellNumber(k)));
		}
		_bellNumbers.put(n, result);
		return result;
	}
}
